package 预测赢家;

/**
 * 预测赢家
 * <p>
 * 给定一个表示分数的非负整数数组。玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端取分数，然后玩家1拿...
 * 每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
 * <p>
 * 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
 * <p>
 * 扩展：石子游戏
 * 贪心算法适用于：局部最优推导出全局最优
 */
public class Solution {
    public static void main(String[] args) {


        canWin1(new int[]{5, 200, 1, 3, 6});
        canWin1(new int[]{5, 200, 2, 3});

        System.out.println();

        canWin2(new int[]{5, 200, 1, 3, 6});
        canWin2(new int[]{5, 200, 2, 3});

        System.out.println();

        canWin3(new int[]{5, 200, 1, 3, 6});
        canWin3(new int[]{5, 200, 2, 3});

        System.out.println();

        canWin4(new int[]{5, 200, 1, 3, 6});
        canWin4(new int[]{5, 200, 2, 3});

    }
    /**
     * 动态规则
     */
    private static void canWin4(int[] scores) {
        int length = scores.length;
        int[] dp = new int[length];

        for (int i = 0; i < length; i++) {
            dp[i] = scores[i];
        }

        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[j] = Math.max(scores[i] - dp[j], scores[j] - dp[j - 1]);
            }
        }

        int score = dp[length - 1];
        System.out.println("score = " + score + ", win = " + (score > 0));
    }

    /**
     * 动态规则
     */
    private static void canWin3(int[] scores) {
        int length = scores.length;
        int[][] dp = new int[length][length];

        for (int i = 0; i < length; i++) {
            dp[i][i] = scores[i];
        }

        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = Math.max(scores[i] - dp[i + 1][j], scores[j] - dp[i][j - 1]);
            }
        }

        int score = dp[0][length - 1];
        System.out.println("score = " + score + ", win = " + (score > 0));
    }

    /**
     * 输赢的分数
     */
    private static void canWin2(int[] scores) {
        // 获取输赢的分数
        int score = getMaxScore1(scores, 0, scores.length - 1);
        System.out.println("score = " + score + ", win = " + (score > 0));
    }

    private static void canWin1(int[] scores) {
        int sum = 0;
        for (int score : scores) {
            sum += score;
        }

        int score = getMaxScore(scores, 0, scores.length - 1);
        System.out.println("score = " + score + ", win = " + (sum - score < score));
    }

    /**
     * 递归法
     * 递归结束条件：
     * l = r 只有1个元素，只能选这个
     * r - l 只有2个元素，只能选较大元素
     * <p>
     * 递归三条件：统计分值，出口，范围递减的等式
     */
    public static int getMaxScore(int[] scores, int l, int r) {
        if (l == r) {
            return scores[l];
        }

        // 我方选左边的总分数
        int sl = 0;
        // 我方选右边的总分数
        int sr = 0;
        if (r - l >= 1) {
            sl = scores[l];
            sr = scores[r];
        }
        if (r - l > 1) {
            int score = getMaxScore(scores, l + 1, r - 1);
            // 我方选左边，计算对方两边最小分数
            sl += Math.min(getMaxScore(scores, l + 2, r), score);
            // 我方选右边，计算对方两边最小分数
            sr += Math.min(score, getMaxScore(scores, l, r - 2));
        }
        // 返回较高分数
        return Math.max(sl, sr);
    }

    public static int getMaxScore1(int[] scores, int l, int r) {
        if (l == r) {
            return scores[l];
        }

        int sl = scores[l] - getMaxScore1(scores, l + 1, r);
        int sr = scores[r] - getMaxScore1(scores, l, r - 1);
        return Math.max(sl, sr);
    }

}
